﻿/***************************************************************************

Copyright (c) Microsoft Corporation 2009.

This code is licensed using the Microsoft Public License (Ms-PL).  The text of the license
can be found here:

http://www.microsoft.com/resources/sharedsource/licensingbasics/publiclicense.mspx

***************************************************************************/

#define ValidateWhileMerging

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Xml;
using System.Xml.Linq;
using DocumentFormat.OpenXml.Packaging;

/// Comparing Documents:
/// 
/// This module contains a function, DocumentComparer.CompareDocuments, that reports whether
/// two documents contain the same content if we disregard comments, or any of the markup
/// that may have been altered if comments are added.
/// 
/// When a document is locked, restricting changes to only the ability to add comments, the
/// area of the markup that is altered is completely around runs.  Runs are split, comment
/// markup is inserted, w:proofErr elements may be added.  One other aspect of markup may be
/// altered, based on the producing application - w:hyperlink elements may be converted to
/// runs that contain w:fldChar elements, again in the area of runs.
/// 
/// There are many elements that can contain runs, and therefore can contain markup that is
/// modified by adding comments.  Examples include paragraphs, content controls, custom XML
/// elements, and more.  oMath elements contain m:r runs that contain m:t text elements.
/// Other than a different namespace, we can handle math markup in exactly the same way as
/// for word processing markup.
/// 
/// Instead of trying to find all elements in the specification that can contain runs that
/// need to be transformed when moving comments, we can write code in a different way -
/// instead of keying off of the element name that contains runs, we key off whether any
/// element contains runs.  The document can contain any of the elements that might possibly
/// contain runs, and the code will behave properly.  This is one approach to building
/// Open XML applications with a high degree of reliability.  There are some small
/// inefficiencies in writing code like this.  However, the reliability that we gain is well
/// worth the performance loss.
/// 
/// Pseudo Code for Determining Document Equivalency
/// 
/// Function: CompareDocuments
///   call function CompareOpenXmlElements, passing root elements of both documents
///
/// Function: CompareOpenXmlElements
///   if elements don't have same name, return false
///   if element1 has either word or math runs
///     call function CompareElementsWithRuns
///   if element1 has text nodes but no child elements, then compare values
///   if both elements are empty, elements are equivalent
///   filter out:
///     W.commentRangeStart
///     W.commentRangeEnd
///     W.proofErr
///     W.rsid
///     and recursively call CompareOpenXmlElements
/// 
/// Function: CompareElementsWithRuns
///   Filter child elements, removing
///     W.commentRangeStart
///     W.commentRangeEnd
///     W.rsid
///     W.proofErr
///     W.fldChar
///     W.hyperlink
///   GroupAdjacent both collections, grouping all word runs, all math runs, and everything
///     else.
///   If the count of the two sets of groups is different, then documents are different.
///   Zip the two collections of collections, passing pairs of collections to:
///     CompareRunsCollections
///     CompareOtherCollections
///   If either return false, the documents differ
///   
///  Function: CompareRunCollections
///    To compare two collections of runs:
///    Get collection of child elements of all runs in the collection.
///    Filter out:
///    - w:rPr
///    - w:commentReference
///    - w:rsid
///    - w:proofErr
///    GroupAdjacent, key = word text elements, math text elements, other
///    To compare two groups of collections of text elements, concat and compare
///    
///  Function: CompareOtherCollections
///    To compare two groups of collections of other elements
///      recursively call CompareOpenXmlElements for each pair.
/// 
/// w:tab is child of w:r, tabs are like text - should show up in same place in content.
/// w:lastRenderedPageBreak is like w:tab - should be in same places in text.
/// 
/// For the purposes of this comparison, don't filter out rev tracking.  The two documents
/// being compared must have rev tracking content in exactly the same places.

public class GroupOfAdjacent<TSource, TKey> : IEnumerable<TSource>, IGrouping<TKey, TSource>
{
    public TKey Key { get; set; }
    private List<TSource> GroupList { get; set; }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return ((System.Collections.Generic.IEnumerable<TSource>)this).GetEnumerator();
    }

    System.Collections.Generic.IEnumerator<TSource>
        System.Collections.Generic.IEnumerable<TSource>.GetEnumerator()
    {
        foreach (var s in GroupList)
            yield return s;
    }

    public GroupOfAdjacent(List<TSource> source, TKey key)
    {
        GroupList = source;
        Key = key;
    }
}

public static class Extensions
{
    public static XDocument GetXDocument(this OpenXmlPart part)
    {
        XDocument partXDocument = part.Annotation<XDocument>();
        if (partXDocument != null)
            return partXDocument;
        using (Stream partStream = part.GetStream())
        using (XmlReader partXmlReader = XmlReader.Create(partStream))
            partXDocument = XDocument.Load(partXmlReader);
        part.AddAnnotation(partXDocument);
        return partXDocument;
    }

    public static void PutXDocument(this OpenXmlPart part)
    {
        XDocument partXDocument = part.GetXDocument();
        if (partXDocument != null)
        {
            using (Stream partStream = part.GetStream(FileMode.Create, FileAccess.Write))
            using (XmlWriter partXmlWriter = XmlWriter.Create(partStream))
                partXDocument.Save(partXmlWriter);
        }
    }

    public static void PutXDocument(this OpenXmlPart part, XDocument document)
    {
        using (Stream partStream = part.GetStream(FileMode.Create, FileAccess.Write))
        using (XmlWriter partXmlWriter = XmlWriter.Create(partStream))
            document.Save(partXmlWriter);
        part.RemoveAnnotations<XDocument>();
        part.AddAnnotation(document);
    }

    public static string StringConcatenate(this IEnumerable<string> source)
    {
        StringBuilder sb = new StringBuilder();
        foreach (string s in source)
            sb.Append(s);
        return sb.ToString();
    }

    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(
        this IEnumerable<TFirst> first,
        IEnumerable<TSecond> second,
        Func<TFirst, TSecond, TResult> func)
    {
        var ie1 = first.GetEnumerator();
        var ie2 = second.GetEnumerator();
        while (ie1.MoveNext() && ie2.MoveNext())
            yield return func(ie1.Current, ie2.Current);
    }

    public static IEnumerable<IGrouping<TKey, TSource>> GroupAdjacent<TSource, TKey>(
        this IEnumerable<TSource> source,
        Func<TSource, TKey> keySelector)
    {
        TKey last = default(TKey);
        bool haveLast = false;
        List<TSource> list = new List<TSource>();

        foreach (TSource s in source)
        {
            TKey k = keySelector(s);
            if (haveLast)
            {
                if (!k.Equals(last))
                {
                    yield return new GroupOfAdjacent<TSource, TKey>(list, last);
                    list = new List<TSource>();
                    list.Add(s);
                    last = k;
                }
                else
                {
                    list.Add(s);
                    last = k;
                }
            }
            else
            {
                list.Add(s);
                last = k;
                haveLast = true;
            }
        }
        if (haveLast)
            yield return new GroupOfAdjacent<TSource, TKey>(list, last);
    }
}

public static class W
{
    public static XNamespace w =
        "http://schemas.openxmlformats.org/wordprocessingml/2006/main";
    public static XName t = w + "t";
    public static XName r = w + "r";
    public static XName rPr = w + "rPr";
    public static XName del = w + "del";
    public static XName body = w + "body";
    public static XName id = w + "id";
    public static XName p = w + "p";
    public static XName moveFrom = w + "moveFrom";
    public static XName commentRangeStart = w + "commentRangeStart";
    public static XName commentRangeEnd = w + "commentRangeEnd";
    public static XName proofErr = w + "proofErr";
    public static XName comments = w + "comments";
    public static XName comment = w + "comment";
    public static XName commentReference = w + "commentReference";
    public static XName rsidTr = w + "rsidTr";
    public static XName rsidSect = w + "rsidSect";
    public static XName rsidRDefault = w + "rsidRDefault";
    public static XName rsidR = w + "rsidR";
    public static XName rsidDel = w + "rsidDel";
    public static XName rsidP = w + "rsidP";
    public static XName rsidRPr = w + "rsidRPr";
    public static XName rsid = w + "rsid";
    public static XName fldChar = w + "fldChar";
    public static XName hyperlink = w + "hyperlink";
    public static XName lastRenderedPageBreak = w + "lastRenderedPageBreak";
}

public static class EP
{
    public static XNamespace ep =
        "http://schemas.openxmlformats.org/officeDocument/2006/extended-properties";
    public static XName DocSecurity = ep + "DocSecurity";
}

public static class M
{
    public static XNamespace m =
        "http://schemas.openxmlformats.org/officeDocument/2006/math";
    public static XName r = m + "r";
    public static XName t = m + "t";
    public static XName oMath = m + "oMath";
    public static XName sty = m + "sty";
    public static XName rPr = m + "rPr";
}

public class DocumentComparerInternalException : Exception
{
    public DocumentComparerInternalException(string message) : base(message) { }
}

public static class DocumentComparer
{
    private enum RunElementType
    {
        WordRun,
        MathRun,
        Other
    };

    private enum RunChildElementType
    {
        WordTextElement,
        MathTextElement,
        Other
    };

    private static bool CompareRunCollections(IEnumerable<XElement> runCollection1,
        IEnumerable<XElement> runCollection2)
    {
        var runChildElementCollection1 = runCollection1
            .Elements()
            .Where(e => e.Name != W.commentRangeStart &&
                e.Name != W.commentRangeEnd &&
                e.Name != W.commentReference &&
                e.Name != W.rPr &&
                e.Name != W.proofErr &&
                e.Name != M.sty &&
                e.Name != M.rPr)
            .GroupAdjacent(e =>
            {
                if (e.Name == W.t)
                    return RunChildElementType.WordTextElement;
                if (e.Name == M.t)
                    return RunChildElementType.MathTextElement;
                return RunChildElementType.Other;
            });
        var runChildElementCollection2 = runCollection2
            .Elements()
            .Where(e => e.Name != W.commentRangeStart &&
                e.Name != W.commentRangeEnd &&
                e.Name != W.commentReference &&
                e.Name != W.rPr &&
                e.Name != W.proofErr &&
                e.Name != M.sty &&
                e.Name != M.rPr)
            .GroupAdjacent(e =>
            {
                if (e.Name == W.t)
                    return RunChildElementType.WordTextElement;
                if (e.Name == M.t)
                    return RunChildElementType.MathTextElement;
                return RunChildElementType.Other;
            });
#if false
        foreach (var item in runChildElementCollection1)
        {
            Console.WriteLine(item.Key);
            foreach (var i2 in item)
            {
                Console.WriteLine(i2.Name.LocalName);
            }
            Console.WriteLine();
        }
        Console.WriteLine();
        foreach (var item in runChildElementCollection2)
        {
            Console.WriteLine(item.Key);
            foreach (var i2 in item)
            {
                Console.WriteLine(i2.Name.LocalName);
            }
            Console.WriteLine();
        }
        Environment.Exit(0);
#endif
        bool different = runChildElementCollection1
            .Zip(runChildElementCollection2, (c1, c2) =>
            {
                if (c1.Key != c2.Key)
                    return false;
                switch (c1.Key)
                {
                    case RunChildElementType.WordTextElement:
                    case RunChildElementType.MathTextElement:
                        string string1 = c1.Select(t => (string)t).StringConcatenate();
                        string string2 = c2.Select(t => (string)t).StringConcatenate();
                        if (string1 == string2)
                            return true;
                        else
                            return false;
                    case RunChildElementType.Other:
                        bool d = c1
                            .Zip(c2, (e1, e2) => new { E1 = e1, E2 = e2 })
                            .Select(z => CompareOpenXmlElements(z.E1, z.E2))
                            .Any(b => b == false);
                        if (d == true)
                            return false;
                        else
                            return true;
                };
                throw new DocumentComparerInternalException(
                    "Should not have reached this code");
            })
            .Any(b => b == false);
        if (different == true)
            return false;
        else
            return true;
    }

    private static bool CompareOtherCollections(IEnumerable<XElement> collection1,
        IEnumerable<XElement> collection2)
    {
        bool different = collection1
            .Zip(collection2, (e1, e2) => new { E1 = e1, E2 = e2 })
            .Select(z => CompareOpenXmlElements(z.E1, z.E2))
            .Any(b => b == false);
        if (different == true)
            return false;
        else
            return true;
    }

    private static bool CompareElementsWithRuns(XElement element1, XElement element2)
    {
        var groupedCollection1 = element1
            .Elements()
            .Where(e => e.Name != W.commentRangeStart &&
                e.Name != W.commentRangeEnd &&
                e.Name != W.rsid &&
                e.Name != W.proofErr &&
                e.Name != W.fldChar &&
                e.Name != W.hyperlink)
            .GroupAdjacent(e =>
            {
                if (e.Name == W.r)
                    return RunElementType.WordRun;
                if (e.Name == M.r)
                    return RunElementType.MathRun;
                return RunElementType.Other;
            });
        var groupedCollection2 = element2
            .Elements()
            .Where(e => e.Name != W.commentRangeStart &&
                e.Name != W.commentRangeEnd &&
                e.Name != W.rsid &&
                e.Name != W.proofErr &&
                e.Name != W.fldChar &&
                e.Name != W.hyperlink)
            .GroupAdjacent(e =>
            {
                if (e.Name == W.r)
                    return RunElementType.WordRun;
                if (e.Name == M.r)
                    return RunElementType.MathRun;
                return RunElementType.Other;
            });
        if (groupedCollection1.Count() != groupedCollection2.Count())
        {
#if false
            // If this test returns false for a document that you think is erroneous,
            // the following will give clues to the markup that may need to be ignored, or
            // the markup that indicates that the documents are different.
            foreach (var item in groupedCollection1)
            {
                Console.WriteLine(item.Key);
                foreach (var item2 in item)
                {
                    Console.WriteLine(item2.Name.LocalName);
                }
                Console.WriteLine();
            }
            Console.WriteLine("==================");
            foreach (var item in groupedCollection2)
            {
                Console.WriteLine(item.Key);
                foreach (var item2 in item)
                {
                    Console.WriteLine(item2.Name.LocalName);
                }
                Console.WriteLine();
            }
            Environment.Exit(0);
#endif
            return false;
        }
        bool different = groupedCollection1
            .Zip(groupedCollection2, (c1, c2) =>
            {
                if (c1.Key != c2.Key)
                    return false;
                switch (c1.Key)
                {
                    case RunElementType.WordRun:
                    case RunElementType.MathRun:
                        return CompareRunCollections(c1, c2);
                    case RunElementType.Other:
                        return CompareOtherCollections(c1, c2);
                };
                throw new DocumentComparerInternalException(
                    "Should not have reached this code");
            })
            .Any(b => b == false);
        if (different == true)
            return false;
        else
            return true;
    }

    // returns true if the elements are the same, otherwise false.
    private static bool CompareOpenXmlElements(XElement element1, XElement element2)
    {
        if (element1.Name != element2.Name)
            return false;
        if (element1
            .Elements()
            .Where(e => e.Name == W.r || e.Name == M.r)
            .Any())
            return CompareElementsWithRuns(element1, element2);
        if (element1.Nodes().OfType<XText>().Any() &&
            !element1.HasElements)
        {
            if (element1.Value == element2.Value)
                return true;
            else
                return false;
        }
        if (element1.IsEmpty && element2.IsEmpty)
            return true;
        var c1 = element1
            .Elements()
            .Where(e => e.Name != W.commentRangeStart &&
                e.Name != W.commentRangeEnd &&
                e.Name != W.proofErr &&
                e.Name != W.rsid);
        var c2 = element2
            .Elements()
            .Where(e => e.Name != W.commentRangeStart &&
                e.Name != W.commentRangeEnd &&
                e.Name != W.proofErr &&
                e.Name != W.rsid);
        var different = c1
            .Zip(c2, (e1, e2) => new { E1 = e1, E2 = e2 })
            .Select(p => CompareOpenXmlElements(p.E1, p.E2))
            .Any(b => b == false);
        if (different == true)
            return false;
        else
            return true;
    }

    // Returns true if docs are the same, otherwise false.
    public static bool CompareDocuments(WordprocessingDocument doc1,
        WordprocessingDocument doc2)
    {
        return CompareOpenXmlElements(doc1.MainDocumentPart.GetXDocument().Root,
            doc2.MainDocumentPart.GetXDocument().Root);
    }
}

public class CommentMergerInternalException : Exception
{
    public CommentMergerInternalException(string message) : base(message) { }
}

public class CommentMergerDifferingContentsException : Exception
{
    public CommentMergerDifferingContentsException(string message) : base(message) { }
}

public class CommentMergerUnlockedDocumentException : Exception
{
    public CommentMergerUnlockedDocumentException(string message) : base(message) { }
}

public class CommentMerger
{
    // TransformCommentReference takes a w:commentRangeStart, w:commentRangeEnd, or
    // special comment reference run and returns a new one where the id has been adjusted
    // appropriately for insertion into the merged document.
    //
    // The elements look like this:
    //
    // <w:commentRangeStart w:id="0" />
    //
    // <w:commentRangeEnd w:id="0" />
    //
    // <w:r>
    //   <w:rPr>
    //     <w:rStyle w:val="CommentReference" />
    //   </w:rPr>
    //   <w:commentReference w:id="0" />
    // </w:r>
    private static XElement TransformCommentReference(XElement element,
        Dictionary<string, string> commentIdTransformDictionary)
    {
        if (element.Name == W.commentRangeStart || element.Name == W.commentRangeEnd)
            return new XElement(element.Name,
                new XAttribute(W.id,
                    commentIdTransformDictionary[element.Attribute(W.id).Value]));
        if ((element.Name == W.r || element.Name == M.r) &&
                element.Elements(W.commentReference).Any())
            return new XElement(element.Name,
                element.Elements().Where(e => e.Name != W.commentReference),
                new XElement(W.commentReference,
                    new XAttribute(W.id,
                        commentIdTransformDictionary[
                        element.Element(W.commentReference).Attribute(W.id).Value])));
        return element;
    }

    // This is a utility method used for correctly adding xml:space='preserve'.
    private static XAttribute XmlSpacePreserved(string value)
    {
        if (value.Substring(0, 1) == " " || value.Substring(value.Length - 1) == " ")
            return new XAttribute(XNamespace.Xml + "space", "preserve");
        else
            return null;
    }

    private class ElementWithLocation
    {
        public XElement Element { get; set; }
        public string RunText { get; set; }
        public int Location { get; set; }
        public int Length { get; set; }
        public bool FromDocument { get; set; }
    }

    private static XElement CloneElementWithComments(XElement toElement,
        XElement fromElement, Dictionary<string, string> commentIdTransformDictionary)
    {
        XName runName;
        XName textName;
        if (toElement.Name.Namespace == W.w)
        {
            runName = W.r;
            textName = W.t;
        }
        else
        {
            runName = M.r;
            textName = M.t;
        }
        // Get a collection of comment elements from the 'from' document that need to be
        // transfered to the 'to' document.
        var fromElementCommentMarkup = fromElement
            .Elements()
            .Where(e => e.Name == W.commentRangeStart ||
                e.Name == W.commentRangeEnd ||
                (e.Name == runName &&
                    e.Elements(W.commentReference).Any()));

        // Determine the location in text of each of the elements that need to be
        // transfered to the 'to' document.
        var fromCommentMarkupWithLocation = fromElementCommentMarkup
            .Select(e =>
                new ElementWithLocation()
                {
                    Element = e,
                    RunText = e.Elements()
                        .Where(z => z.Name == textName)
                        .Select(z => (string)z)
                        .StringConcatenate(),
                    Location = e
                        .ElementsBeforeSelf()
                        .Elements()
                        .Where(z => z.Name == textName)
                        .Select(z => (string)z)
                        .StringConcatenate()
                        .Length,
                    Length = e.Elements()
                        .Where(z => z.Name == textName)
                        .Select(z => (string)z)
                        .StringConcatenate()
                        .Length,
                    FromDocument = true
                }
            );

        // Create a dictionary of corresponding elements so that the code can invoke the
        // recursive transform for elements other than runs and comment elements.
        var toGroupedCollection = toElement
            .Elements()
            .Where(e => e.Name != W.commentRangeStart &&
                e.Name != W.commentRangeEnd &&
                e.Name != W.rsid &&
                e.Name != W.proofErr &&
                e.Name != W.fldChar &&
                e.Name != W.hyperlink &&
                e.Name != runName);
        var fromGroupedCollection = fromElement
            .Elements()
            .Where(e => e.Name != W.commentRangeStart &&
                e.Name != W.commentRangeEnd &&
                e.Name != W.rsid &&
                e.Name != W.proofErr &&
                e.Name != W.fldChar &&
                e.Name != W.hyperlink &&
                e.Name != runName);
#if ValidateWhileMerging
        if (toGroupedCollection.Count() != fromGroupedCollection.Count())
        {
#if false
            // If this test returns false for a document that you think is erroneous,
            // the following will give clues to the markup that may need to be ignored, or
            // the markup that indicates that the documents are different.
            foreach (var item in toGroupedCollection)
            {
                Console.WriteLine(item.Name.LocalName);
            }
            Console.WriteLine("==================");
            foreach (var item in fromGroupedCollection)
            {
                Console.WriteLine(item.Name.LocalName);
            }
#endif
            throw new CommentMergerInternalException("Since documents compared as " +
                "equivalent, the above queries should return collections of the same length");
        }
#endif
        Dictionary<XElement, XElement> correspondingElements = toGroupedCollection
            .Zip(fromGroupedCollection, (e1, e2) => new { E1 = e1, E2 = e2 })
            .ToDictionary(k => k.E1, e => e.E2);

        // Create a list of elements (with location information) so that can determine which
        // runs need to be split.
        var elementsWithLocation = toElement
            .Elements()
            .Select(e => new ElementWithLocation
            {
                Element = e,
                RunText = e.Elements()
                    .Where(z => z.Name == textName)
                    .Select(z => (string)z)
                    .StringConcatenate(),
                Location = e.ElementsBeforeSelf()
                    .Elements()
                    .Where(z => z.Name == textName)
                    .Select(t => (string)t)
                    .StringConcatenate()
                    .Length,
                Length = e.Elements()
                    .Where(z => z.Name == textName)
                    .Select(t => (string)t)
                    .StringConcatenate()
                    .Length,
                FromDocument = false
            })
            .Concat(fromCommentMarkupWithLocation)
            .OrderBy(i => i.Location)
            .ToList();

        // Create a new list of elements (with location information), where all runs that
        // need to be split are split.
        var newElementsWithLocation = elementsWithLocation
            .Select(e =>
            {
                // if the run needs split
                if (elementsWithLocation
                    .Where(z => z.Location > e.Location &&
                        z.Location < e.Location + e.Length)
                    .Any())
                {
                    // need to split run
                    int[] splitLocations = new[] { e.Location }
                        .Concat(elementsWithLocation
                            .Where(z => z.Location > e.Location &&
                                z.Location < e.Location + e.Length)
                            .Select(z => z.Location)
                            .Distinct())
                        .ToArray();

                    var textOfSplitRuns = splitLocations
                        .Select((sl, i) => new
                        {
                            Text = i != splitLocations.Length - 1 ?
                                e.RunText.Substring(sl - e.Location,
                                    splitLocations[i + 1] - sl) :
                                e.RunText.Substring(sl - e.Location),
                            Location = sl
                        });

                    return textOfSplitRuns
                        .Select(t => new ElementWithLocation
                        {
                            Element = new XElement(runName,
                                e.Element.Elements().Where(q => q.Name != textName),
                                new XElement(textName,
                                    XmlSpacePreserved(t.Text),
                                    t.Text)),
                            RunText = t.Text,
                            Location = t.Location,
                            Length = 0,
                            FromDocument = false
                        });
                }
                else
                    return (IEnumerable<ElementWithLocation>)
                        new List<ElementWithLocation>() { e };
            })
            .ToList()
            .SelectMany(c => c)
            .OrderBy(y => y.Location)
            .ThenBy(x =>
            {
                if (x.Element.Name != runName)
                    return 0;
                if (x.Element.Name == runName &&
                    x.Element.Elements(W.commentReference).Any())
                    return 1;
                return 2;
            });

        // Create the new element to be inserted into the 'to' document, where all comment
        // elements from the 'from' document have their Ids transformed appropriately, and
        // all elements that need to be recursively transformed are transformed.
        XElement newToElement = new XElement(toElement.Name,
            toElement.Attributes(),
            newElementsWithLocation
                .Select(e =>
                {
                    if (correspondingElements.ContainsKey(e.Element))
                        return MergeCommentsTransform(e.Element,
                            correspondingElements[e.Element], commentIdTransformDictionary);
                    else
                    {
                        if (e.FromDocument)
                            return TransformCommentReference(e.Element,
                                commentIdTransformDictionary);
                        else
                            return e.Element;
                    }
                }));

#if false
        fromElement.Add(
            new XAttribute(XNamespace.Xmlns + "m", M.m),
            new XAttribute(XNamespace.Xmlns + "w", W.w));
        Console.WriteLine(fromElement);
        Console.WriteLine("==========================================");
        newToElement.Add(
            new XAttribute(XNamespace.Xmlns + "m", M.m),
            new XAttribute(XNamespace.Xmlns + "w", W.w));
        Console.WriteLine(newToElement);
        Console.WriteLine(XNode.DeepEquals(fromElement, newToElement));
#endif

        return newToElement;
    }

    // Recursive transform for entire document.
    private static object MergeCommentsTransform(XNode toNode, XNode fromNode,
        Dictionary<string, string> commentIdTransformDictionary)
    {
        XElement toElement = toNode as XElement;
        XElement fromElement = fromNode as XElement;

#if ValidateWhileMerging
        if ((toElement != null) != (fromElement != null))
            throw new CommentMergerInternalException(
                "Since documents compared as equivalent, both nodes should be XElement " +
                "objects, or both should not be XElement objects.");
#endif

        if (toElement != null)
        {
#if ValidateWhileMerging
            if (toElement.IsEmpty != fromElement.IsEmpty)
                throw new CommentMergerInternalException("Since documents compared as" +
                    "Equivalent, both elements should be empty, or both elements should " +
                    "not be");
            if (toElement.Name != fromElement.Name)
                throw new CommentMergerInternalException("Since documents compared as" +
                    "Equivalent, elements should have the same name");
#endif

            // If element is empty, then clone element.
            if (toElement.IsEmpty)
                return toElement;

#if ValidateWhileMerging
            if (toElement.Nodes().OfType<XText>().Any() &&
                !toElement.HasElements)
            {
                if (!(fromElement.Nodes().OfType<XText>().Any() &&
                    !fromElement.HasElements))
                    throw new CommentMergerInternalException("Since documents compared as" +
                        "Equivalent, both elements should contain text content, or both " +
                        "elements should contain child elements");
            }
#endif
            // If element contains only text nodes, then clone element.
            if (toElement.Nodes().OfType<XText>().Any() &&
                !toElement.HasElements)
                return toElement;

            // If fromElement contains comments, then do special clone that merges comments.
            if (fromElement
                .Elements()
                .Where(e => e.Name == W.commentRangeStart ||
                    e.Name == W.commentRangeEnd ||
                    ((e.Name == W.r || e.Name == M.r) &&
                        e.Elements(W.commentReference).Any()
                        ))
                .Any())
            {
                // Get new, cloned element with merged comments.
                XElement newToElement = CloneElementWithComments(toElement, fromElement,
                    commentIdTransformDictionary);
                return newToElement;
            }

            // Clone elements other than those with comment markup.
            var c1 = toElement
                .Elements()
                .Where(e => e.Name != W.proofErr &&
                    e.Name != W.lastRenderedPageBreak &&
                    e.Name != W.r &&
                    e.Name != M.r &&
                    e.Name != W.hyperlink);
            var c2 = fromElement
                .Elements()
                .Where(e => e.Name != W.proofErr &&
                    e.Name != W.lastRenderedPageBreak &&
                    e.Name != W.r &&
                    e.Name != M.r &&
                    e.Name != W.hyperlink);

            var ce = c1.Zip(c2, (e1, e2) => new { E1 = e1, E2 = e2 })
                .ToDictionary(k => k.E1, e => e.E2);

            return new XElement(toElement.Name,
                toElement.Attributes(),
                toElement
                    .Elements()
                    .Select(p =>
                    {
                        if (ce.ContainsKey(p))
                            return MergeCommentsTransform(p, ce[p],
                                commentIdTransformDictionary);
                        else
                            return p;
                    }));
        }
        return toNode;
    }

    /// <summary>
    /// Merges comments from two documents into one.
    /// </summary>
    /// <param name="toDocument">
    /// Specifies the destination document.  After transform,
    /// toDocument contains all comments from the 'from' document and the 'to' document.
    /// </param>
    /// <param name="fromDocument">
    /// Specifies the source document.  This document isn't modified.
    /// </param>
    public static void MergeComments(WordprocessingDocument toDocument,
        WordprocessingDocument fromDocument)
    {
        XDocument toXDocument = toDocument.MainDocumentPart.GetXDocument();
        XDocument fromXDocument = fromDocument.MainDocumentPart.GetXDocument();

        // If the 'from' document doesn't contain a comments part, nothing to do.
        if (fromDocument.MainDocumentPart.WordprocessingCommentsPart == null)
            return;

        // If documents don't contain the same content, then don't attempt to merge comments.
        bool same = DocumentComparer.CompareDocuments(toDocument, fromDocument);
        if (!same)
            throw new CommentMergerDifferingContentsException(
                "Documents do not contain the same content");

        // If either document is not locked (allowing only commenting), don't attempt to
        // merge comments.
        if (toDocument.ExtendedFilePropertiesPart.GetXDocument().Root
            .Element(EP.DocSecurity).Value != "8")
            throw new CommentMergerUnlockedDocumentException(
                "Destination document is not locked");
        if (fromDocument.ExtendedFilePropertiesPart.GetXDocument().Root
            .Element(EP.DocSecurity).Value != "8")
            throw new CommentMergerUnlockedDocumentException(
                "Source document is not locked");

        // If there is no comments part in the 'to' document, then add and initialize one.
        if (toDocument.MainDocumentPart.WordprocessingCommentsPart == null)
        {
            WordprocessingCommentsPart commentsPart =
                toDocument.MainDocumentPart.AddNewPart<WordprocessingCommentsPart>();
            XDocument xdoc = new XDocument(
                new XElement(W.comments)
            );
            commentsPart.PutXDocument(xdoc);
        }

        // Get the XDocuments for the two comments parts.
        XDocument toWordprocessingCommentsXDocument = toDocument
            .MainDocumentPart
            .WordprocessingCommentsPart
            .GetXDocument();
        XDocument fromWordprocessingCommentsXDocument = fromDocument
            .MainDocumentPart
            .WordprocessingCommentsPart
            .GetXDocument();

        // Compute the start of the comment ids of the comments that are merged into the
        // 'to' document.  Determine highest comment id in current document, and add one,
        // otherwise init to zero. 
        var toDocumentCommentIds = toWordprocessingCommentsXDocument
            .Root
            .Elements(W.comment)
            .Attributes(W.id).Select(a =>
            {
                int id;
                if (!Int32.TryParse((string)a, out id))
                    id = 0;
                return id;
            });
        int startCommentId;
        if (toDocumentCommentIds.Any())
            startCommentId = toDocumentCommentIds.Max() + 1;
        else
            startCommentId = 0;

        // Create a dictionary that maps comment ids in the 'from' document to their new
        // comment ids in the newly merged document.
        Dictionary<string, string> commentIdTransformDictionary =
            fromWordprocessingCommentsXDocument
            .Root
            .Elements(W.comment)
            .Attributes(W.id)
            .Select((i, j) => new
            {
                Id = (string)i,
                Index = j
            })
            .ToDictionary(k => k.Id, e => (e.Index + startCommentId).ToString());

        // Create a new XDocument for the merged comments part that contains comments from
        // both the 'from' and 'to' document.
        XDocument newMergedCommentsXDocument = new XDocument(
            new XElement(W.comments,
                toWordprocessingCommentsXDocument.Root.Attributes(),
                toWordprocessingCommentsXDocument.Root.Elements(),
                fromWordprocessingCommentsXDocument
                    .Root
                    .Elements()
                    .Select(c => new XElement(W.comment,
                        new XAttribute(W.id,
                            commentIdTransformDictionary[c.Attribute(W.id).Value]),
                        c.Attributes().Where(a => a.Name != W.id),
                        c.Elements()))));

        // Save it back to its part.
        toDocument.MainDocumentPart
            .WordprocessingCommentsPart
            .PutXDocument(newMergedCommentsXDocument);

        // Produce a new document with merged comment markup.
        XDocument newToXDocument = new XDocument(
            MergeCommentsTransform(toXDocument.Root, fromXDocument.Root,
            commentIdTransformDictionary)
        );

        // Write the document with merged comments back to its part.
        toDocument.MainDocumentPart.PutXDocument(newToXDocument);
    }
}
